<!doctype html public "-//W3C//DTD HTML 4.0 Transitional//EN" "http://www.w3.org/TR/REC-html40/loose.dtd">
<html>
<!-- Generated from TeX source by tex2page, v 4o, 
     (c) Dorai Sitaram, http://www.cs.rice.edu/~dorai/tex2page -->
<head>
<title>
Structure and Interpretation 
of Computer Programs
</title>
<link rel="stylesheet" type="text/css" href="book-Z-C.css" title=default>
<meta name=robots content="noindex,follow">
</head>
<body>

<p><div class=navigation>[Go to <span><a href="book.html">first</a>, <a href="book-Z-H-24.html">previous</a></span><span>, <a href="book-Z-H-26.html">next</a></span> page<span>; &nbsp;&nbsp;</span><span><a href="book-Z-H-4.html#%_toc_start">contents</a></span><span><span>; &nbsp;&nbsp;</span><a href="book-Z-H-38.html#%_index_start">index</a></span>]</div><p>

<a name="%_chap_4"></a>
<h1 class=chapter>
<div class=chapterheading><a href="book-Z-H-4.html#%_toc_%_chap_4">Chapter 4</a></div><p>
<a href="book-Z-H-4.html#%_toc_%_chap_4">Metalinguistic Abstraction</a></h1><p>

<p>
<div align=right> 
<table width=60%><tr><td>
<span class=epigraph>
<p>

<tt>...</tt> It's in words that the magic
is -- Abracadabra, Open Sesame, and the rest -- but the magic words in
one story aren't magical in the next.  The real magic is to understand
which words work, and when, and for what; the trick is to learn the
trick.<br>
<tt>...</tt> And those words are made from the letters of our
alphabet: a couple-dozen squiggles we can draw with the pen.  This is
the key!  And the treasure, too, if we can only get our hands on it!
It's as if -- as if the key to the treasure <em>is</em> the treasure!<p>

<a name="%_idx_4188"></a>John Barth, <em>Chimera</em><p>

</span>
</td></tr></table>
</div>

<p><p>

In our study of program design, we have seen that expert programmers
control the complexity of their designs with the same general
techniques used by designers of all complex systems.  They combine
primitive elements to form compound objects, they abstract compound
objects to form higher-level building blocks, and they preserve
modularity by adopting appropriate large-scale views of system
structure.  In illustrating these techniques, we have used Lisp as a
language for describing processes and for constructing computational
data objects and processes to model complex phenomena in the real
world.  However, as we confront increasingly complex problems, we will
find that Lisp, or indeed any fixed programming language, is not
sufficient for our needs.  We must constantly turn to new languages in
order to express our ideas more effectively.  Establishing new
languages is a powerful strategy for controlling complexity in
engineering design; we can often enhance our ability to deal with a
complex problem by adopting a new language that enables us to describe
(and hence to think about) the problem in a different way, using
primitives, means of combination, and means of abstraction that are
particularly well suited to the problem at hand.<a name="call_footnote_Temp_508" href="#footnote_Temp_508"><sup><small>1</small></sup></a><p>

<a name="%_idx_4190"></a><a name="%_idx_4192"></a>Programming is endowed with a multitude of languages.  There are
physical languages, such as the machine languages for particular
computers.  These languages are concerned with the representation of
data and control in terms of individual bits of storage and primitive
machine instructions.  The machine-language programmer is concerned
with using the given hardware to erect systems and utilities for the
efficient implementation of resource-limited computations.  High-level
languages, erected on a machine-language substrate, hide concerns
about the representation of data as collections of bits and the
representation of programs as sequences of primitive instructions.
These languages have means of combination and abstraction, such as
procedure definition, that are appropriate to the larger-scale
organization of systems.<p>

<a name="%_idx_4194"></a><a name="%_idx_4196"></a><em>Metalinguistic abstraction</em> -- establishing new
languages -- plays an important role in all branches of engineering
design.  It is particularly important to computer programming, because
in programming not only can we formulate new languages but we can also
implement these languages by constructing evaluators.  An <a name="%_idx_4198"></a><em>evaluator</em> (or <em>interpreter</em>) for a programming language is a procedure
that, when applied to an expression of the language, performs the
actions required to evaluate that expression.<p>

It is no exaggeration to regard this as the most fundamental idea in
programming:
<blockquote>
The evaluator, which determines the meaning of expressions in a
programming language, is just another program.
</blockquote>
To appreciate this point is to change our images of ourselves as
programmers.  We come to see ourselves as designers of languages,
rather than only users of languages designed by others.<p>


In fact, we can regard almost any program as the evaluator for some
language.  For instance, the polynomial manipulation system of
section&nbsp;<a href="book-Z-H-18.html#%_sec_2.5.3">2.5.3</a> embodies the rules of polynomial
arithmetic and implements them in terms of operations on
list-structured data.  If we augment this system with procedures to
read and print polynomial expressions, we have the core of a
special-purpose language for dealing with problems in symbolic
mathematics.  The digital-logic simulator of
section&nbsp;<a href="book-Z-H-22.html#%_sec_3.3.4">3.3.4</a> and the constraint propagator of
section&nbsp;<a href="book-Z-H-22.html#%_sec_3.3.5">3.3.5</a> are legitimate languages in their own
right, each with its own primitives, means of combination, and means
of abstraction.  Seen from this perspective, the technology for coping
with large-scale computer systems merges with the technology for
building new computer languages, and <a name="%_idx_4200"></a>computer science itself becomes
no more (and no less) than the discipline of constructing appropriate
descriptive languages.<p>

We now embark on a tour of the technology by which languages are
established in terms of other languages.  In this chapter we shall use
Lisp as a base, implementing evaluators as Lisp procedures.  <a name="%_idx_4202"></a>Lisp is
particularly well suited to this task, because of its ability to
represent and manipulate symbolic expressions.  We will take the first
step in understanding how languages are implemented by building an
evaluator for Lisp itself.  The language implemented by our evaluator
will be a subset of the Scheme dialect of Lisp that we use in this
book.  Although the evaluator described in this chapter is written for
a particular dialect of Lisp, it contains the essential structure of
an evaluator for any expression-oriented language designed for writing
programs for a sequential machine.  (In fact, most language processors
contain, deep within them, a little ``Lisp'' evaluator.)  The
evaluator has been simplified for the purposes of illustration and
discussion, and some features have been left out that would be
important to include in a production-quality Lisp system.
Nevertheless, this simple evaluator is adequate to execute most of the
programs in this book.<a name="call_footnote_Temp_509" href="#footnote_Temp_509"><sup><small>2</small></sup></a><p>


An important advantage of making the evaluator accessible as a Lisp
program is that we can implement alternative evaluation rules by
describing these as modifications to the evaluator program.  One place
where we can use this power to good effect is to gain extra control
over the ways in which computational models embody the notion of time,
which was so central to the discussion in chapter&nbsp;3.  There, we
mitigated some of the complexities of state and assignment by using
streams to decouple the representation of time in the world from time
in the computer.  Our stream programs, however, were
sometimes cumbersome, because they were constrained by
the applicative-order evaluation of Scheme.
In section&nbsp;<a href="book-Z-H-27.html#%_sec_4.2">4.2</a>, we'll change
the underlying language to provide for a more elegant approach, by modifying
the evaluator to provide for <em>normal-order evaluation</em>.<p>

Section&nbsp;<a href="book-Z-H-28.html#%_sec_4.3">4.3</a> implements a more
ambitious linguistic change, whereby expressions have many values,
rather than just a single value.  In this language of <em>nondeterministic computing</em>, it is natural to express processes that
generate all possible values for expressions and then search for those
values that satisfy certain constraints.  In terms of models of
computation and time, this is like having time branch into a set of
``possible futures'' and then searching for appropriate time lines.
With our nondeterministic evaluator, keeping track of multiple values
and performing searches are handled automatically by the underlying
mechanism of the language.<p>

In section&nbsp;<a href="book-Z-H-29.html#%_sec_4.4">4.4</a> we implement a <em>logic-programming</em> language in which knowledge is expressed in terms
of relations, rather than in terms of computations with inputs and
outputs.  Even though this makes the language drastically different
from Lisp, or indeed from any conventional language, we will see that
the logic-programming evaluator shares the essential structure of the
Lisp evaluator.<p>

<p><div class=smallprint><hr></div><p>
<div class=footnote><p><a name="footnote_Temp_508" href="#call_footnote_Temp_508"><sup><small>1</small></sup></a> The same idea
is pervasive throughout all of engineering.  For example, electrical
engineers use many different languages for describing circuits.  Two
of these are the language of electrical <em>networks</em> and the
language of electrical <em>systems</em>.  The network language emphasizes
the physical modeling of devices in terms of discrete electrical
elements.  The primitive objects of the network language are primitive
electrical components such as resistors, capacitors, inductors, and
transistors, which are characterized in terms of physical variables
called voltage and current.  When describing circuits in the network
language, the engineer is concerned with the physical characteristics
of a design.  In contrast, the primitive objects of the system
language are signal-processing modules such as filters and amplifiers.
Only the functional behavior of the modules is relevant, and signals
are manipulated without concern for their physical realization as
voltages and currents.  The system language is erected on the network
language, in the sense that the elements of signal-processing systems
are constructed from electrical networks.  Here, however, the concerns
are with the large-scale organization of electrical devices to solve a
given application problem; the physical feasibility of the parts is
assumed.  This layered collection of languages is another example of
the stratified design technique illustrated by the picture
language of section&nbsp;<a href="book-Z-H-15.html#%_sec_2.2.4">2.2.4</a>.

<p><a name="footnote_Temp_509" href="#call_footnote_Temp_509"><sup><small>2</small></sup></a> The most important features that our evaluator leaves out
are mechanisms for handling errors and supporting debugging.  For a
more extensive discussion of evaluators, see <a name="%_idx_4204"></a><a name="%_idx_4206"></a><a name="%_idx_4208"></a>Friedman, Wand, and Haynes
1992, which gives an exposition of programming languages that proceeds
via a sequence of evaluators written in Scheme.

</div>

<p><div class=navigation>[Go to <span><a href="book.html">first</a>, <a href="book-Z-H-24.html">previous</a></span><span>, <a href="book-Z-H-26.html">next</a></span> page<span>; &nbsp;&nbsp;</span><span><a href="book-Z-H-4.html#%_toc_start">contents</a></span><span><span>; &nbsp;&nbsp;</span><a href="book-Z-H-38.html#%_index_start">index</a></span>]</div><p>

</body>
</html>
